package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * 1335. 工作计划的最低难度
 * c
 * dp
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/4 10:18
 */
public class MinDifficulty {

    public static void main(String[] args) {
        MinDifficulty test = new MinDifficulty();

        // 7
//        int[] jobDifficulty = {6, 5, 4, 3, 2, 1};
//        int d = 2;

        // -1
//        int[] jobDifficulty = {9, 9, 9};
//        int d = 4;

        // 3
//        int[] jobDifficulty = {1, 1, 1};
//        int d = 3;

        // 15
//        int[] jobDifficulty = {7, 1, 7, 1, 7, 1};
//        int d = 3;

        // 843
        int[] jobDifficulty = {11, 111, 22, 222, 33, 333, 44, 444};
        int d = 6;

        int i = test.minDifficulty(jobDifficulty, d);
        System.out.println(i);
    }

    public int minDifficulty(int[] jobDifficulty, int d) {
        int length = jobDifficulty.length;
        if (length < d) {
            return -1;
        }
        int[][] item = new int[length][length];
        for (int i = 0; i < length; i++) {
            int max = jobDifficulty[i];
            item[i][i] = max;
            for (int j = i + 1; j < length; j++) {
                max = Math.max(max, jobDifficulty[j]);
                item[i][j] = max;
            }
        }
        int[][] arr = new int[length + 1][d + 1];
        for (int i = 1; i <= length; i++) {
            arr[i][1] = item[0][i - 1];
            for (int j = 2; j <= Math.min(i, d); j++) {
                int s = Integer.MAX_VALUE;
                for (int k = j; k <= i; k++) {
                    s = Math.min(s, arr[k - 1][j - 1] + item[k - 1][i - 1]);
                }
                arr[i][j] = s;
            }
        }
        return arr[length][d];
    }

}
